package logic;

//import gui.GraphGUI;

public class ThreeOpt {

	public static Tour threeOpt(Graph g, Tour tour){
		int flip = 0;
		int didnone = 0;
//		GraphGUI gammal=null, mellan=null, ny=null;
//		if(TSPSolver.DEBUG && TSPSolver.SHOWGUI){
//			gammal = new GraphGUI(g, tour, false, true, "Gammal");
//			mellan = new GraphGUI(g, tour, false, true, "mellan");
//			ny = new GraphGUI(g, tour, false, true, "ny");
//		}

		byte fliptype= -1;
		for(int l=0;l<20;l++){
			for(int i=0;i<tour.size() ;i++){
				Vertex t1 = g.vertices[i];
				Vertex t2 = tour.next(t1);
				Vertex t3 = null;
				Vertex t4 = null;
				Vertex t5 = null;
				Vertex t6 = null;
				for(Vertex n1 : t1.topk){
					if(n1==t2){
						continue;
					}
					t3 = n1;
					t4 = tour.prev(t3);
					if(t1==t4){
						t3=null;
						continue;
					}
					if(n1 != t2 && (true || improvingmove(t1,t2,t3,t4,g))){
						for(Vertex n2 : t4.topk){
							if(n2==t1 || n2==t2 || n2==t3){
								continue;
							}
							t5 = n2;
							t6 = tour.prev(t5);
							if(t6==t1 || t6==t2 || t6==t4){
								t5=null;
								continue;
							}
							if(tour.between(t1, t4, t6) && (fliptype = improvingmove(t1,t2,t3,t4,t5,t6,g))!=-1){
								break;
							}else {
								t5 = null;
							}
						}
						if(t5!=null){
							break;
						}
					}
					else {
						t3 = null;
					}
				}
				if(t3!=null && t5 !=null){
					if(fliptype!=-1){
						flip++;					
					}
					
					
					
					if(fliptype==0){
						tour.flip(t1,t2,t3,t4);
						tour.flip(t1,t4,t5,t6);
						tour.flip(t1,t6,t2,t3);
					}
					if(fliptype==1){
						tour.flip(t6,t5,t2,t1);
						tour.flip(t5,t2,t3,t4);
					}
					if(fliptype==2){
						tour.flip(t1,t2,t3,t4);
						tour.flip(t2,t3,t5,t6);
					}
					if(fliptype==3){
						tour.flip(t4,t3,t5,t6);
						tour.flip(t3,t5,t2,t1);
					}
					int k = 0;
				}
				else{
					didnone++;
				}
			}
		}
		if(TSPSolver.DEBUG){
			System.err.println("Completed with "+flip+" flips.");
			System.out.println("Did nothing " + didnone + " times.");
		}
		return tour;
	}
	
	private static boolean improvingmove(Vertex t1, Vertex t2, Vertex t3, Vertex t4, Graph g){
		int u1 = g.distMatrix[t3.index][t4.index];
		int v1 = g.distMatrix[t1.index][t2.index];
		int u2 = g.distMatrix[t1.index][t4.index];
		int v2 = g.distMatrix[t3.index][t2.index];
//		if( u1 + v1 > u2 + v2 ){
//			return true;
//		}
		if(v1 > v2){
			return true;
		}
		return false;
	}
	
	private static byte improvingmove(Vertex t1, Vertex t2, Vertex t3, Vertex t4, Vertex t5, Vertex t6, Graph g){
		int u1 = g.distMatrix[t3.index][t4.index];
		int v1 = g.distMatrix[t1.index][t2.index];
		int w1 = g.distMatrix[t5.index][t6.index];
		int origdist = u1+v1+w1;
		
		int[] dist = new int[4];
		
		// t1-t3-t6-t2-t4-t5
		int u2 = g.distMatrix[t1.index][t3.index];
		int v2 = g.distMatrix[t2.index][t6.index];
		int w2 = g.distMatrix[t4.index][t5.index];
		dist[0] = origdist-(u2+v2+w2);

		// t1-t6-t3-t2-t4-t5
		u2 = g.distMatrix[t1.index][t6.index];
		v2 = g.distMatrix[t2.index][t3.index];
		w2 = g.distMatrix[t4.index][t5.index];
		dist[1] = origdist-(u2+v2+w2);
		
		// t1-t4-t2-t6-t3-t5
		u2 = g.distMatrix[t1.index][t4.index];
		v2 = g.distMatrix[t2.index][t6.index];
		w2 = g.distMatrix[t3.index][t5.index];
		dist[2] = origdist-(u2+v2+w2);
		
		// t1-t3-t6-t4-t2-t5
		u2 = g.distMatrix[t1.index][t3.index];
		v2 = g.distMatrix[t2.index][t5.index];
		w2 = g.distMatrix[t4.index][t6.index];
		dist[3] = origdist-(u2+v2+w2);
		
		byte smallest = 0;
		for(byte i=1;i<dist.length ;i++){
			if(dist[i]>dist[smallest]){
				smallest = i;
			}
		}
		if(dist[smallest]<=0){
			return -1;
		}
		return smallest;
	}
	
	
	
}
